Напишите программу,
которая умеет оперировать с большим количеством деков. Дек – это “очередь с двумя
концами”.
Вход. Первая строка
содержит общее количество команд n (0
≤ n ≤ 150000). Каждая из
следующих n строк содержит описание
команды:
·
“pushfront
A B” –
вставить число B в начало дека A;
·
“pushback
A B” –
вставить число B в конец дека A;
·
“popfront
A” – удалить
первый элемент дека A;
·
“popback
A” – удалить
последний элемент дека A.
Для каждой
команды параметры A и B – целые числа от 1 до 150000 включительно.
Выход. Для каждой
команды popfront или popback выведите удаляемое число. Гарантируется, что перед
выполнением команды удаления соответствующий дек не пуст.
|
Пример входа |
Пример выхода |
|
9 pushfront
1 71819 pushback
2 71820 pushback
1 1 popfront
1 popfront
1 pushfront
2 10 pushback
2 11 popback
2 popback
2 |
71819 1 11 71820 |
РЕШЕНИЕ
структуры
данных - очередь
Поскольку
параметр A не более 150000, то очередей будет не более 150000. Объявим массив
из 150000 структур deque. Промоделируем работу очередей.
Объявим массив очередей.
deque<int> q[150001];
Читаем количество команд n.
cin >>
n;
while (n--)
{
Читаем и обрабатываем текущую команду.
cin >> s >> a;
if (s == "pushback")
{
cin >> b;
q[a].push_back(b);
}
if (s == "pushfront")
{
cin >> b;
q[a].push_front(b);
}
if (s == "popfront")
{
cout << q[a].front() << endl;
q[a].pop_front();
}
if (s == "popback")
{
cout << q[a].back() << endl;
q[a].pop_back();
}
}
Реализуем класс очередь.
class deque
{
private:
struct node
{
int data;
node *next, *prev;
node()
{
prev = next = NULL;
}
node(int a)
{
data = a;
prev = next = NULL;
}
} *Head, *Tail;
public:
deque()
{
Head = Tail = NULL;
}
void push_back(int a)
{
node *p = new node(a);
if(Head == NULL)
Head = Tail = p;
else
{
p->prev = Tail;
p->next = NULL;
Tail->next = p;
Tail = p;
}
}
void push_front(int
a)
{
node *p = new node(a);
if(Head == NULL)
Head = Tail = p;
else
{
p->next = Head;
p->prev = NULL;
Head->prev = p;
Head = p;
}
}
int pop_front(void)
{
node *p = Head;
int r = Head->data;
if(Head == Tail)
Head = Tail = NULL;
else
{
Head = Head->next;
Head->prev = NULL;
}
delete p;
return r;
}
int pop_back(void)
{
node *p = Tail;
int r = Tail->data;
if(Head == Tail)
Head = Tail = NULL;
else
{
Tail = Tail->prev;
Tail->next = NULL;
}
delete p;
return r;
}
int empty(void)
{
return Head == NULL;
}
int front(void)
{
return Head->data;
}
int back(void)
{
return Tail->data;
}
};
Объявим массив классов.
#define MAX 150001
deque q[MAX];
Основная часть программы. Читаем входные данные и
моделируем работу очередей.
scanf("%d\n",&n);
while(n--)
{
scanf("%s %d",s,&a);
if(!strcmp(s,"pushback"))
{
scanf("%d\n",&b);
q[a].push_back(b);
}
if(!strcmp(s,"pushfront"))
{
scanf("%d\n",&b);
q[a].push_front(b);
}
if(!strcmp(s,"popfront"))
{
scanf("\n");
printf("%d\n",q[a].front());
q[a].pop_front() ;
}
if(!strcmp(s,"popback"))
{
scanf("\n");
printf("%d\n",q[a].back());
q[a].pop_back();
}
}
import java.util.*;
public class Main
{
static Deque<Integer> q[];
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
q = new LinkedList[150001];
for(int i = 0; i < 150001;
i++)
q[i] = new LinkedList<Integer>();
int n = con.nextInt();
while (n-- > 0)
{
String s = con.next();
int a = con.nextInt();
if (s.equals("pushback"))
{
int b = con.nextInt();
q[a].addLast(b);
}
if (s.equals("pushfront"))
{
int b = con.nextInt();
q[a].addFirst(b);
}
if (s.equals("popback"))
{
System.out.println(q[a].removeLast());
}
if (s.equals("popfront"))
{
System.out.println(q[a].removeFirst());
}
}
con.close();
}
}